package flashBack;

/**
 * @author zxc
 * @date 2023/01/17 08:51
 **/

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 *  题目 ：包含重复元素集合的组合
 *  题目详述 ：
 *  给定一个可能有重复数字的整数数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
 *  candidates中的每个数字在每个组合中只能使用一次，解集不能包含重复的组合。
 */
public class CombinationSum2 {
    /**
     * 思路 ：
     * 注意的是，需要去避免重复组合
     * 避免重复组合的方法 ：即，当某一步决定跳过某个值m时，需要去跳过所有值为m的数字;
     * @param candidates
     * @param target
     * @return
     */
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        // 对于candidates数组进行排序，便利后续筛选重复组合
        Arrays.sort(candidates);
        List<List<Integer>> result = new LinkedList<>();
        flushBack(candidates , target , 0 , new LinkedList<Integer>() , result);
        return result;
    }
    // 回溯法
    private void flushBack(int[] candidates, int target, int index, LinkedList<Integer> candidate, List<List<Integer>> result) {
        if(target == 0){
            result.add(new LinkedList<Integer>(candidate));
        }
        else if(target > 0 && index < candidates.length){
            // 选择将下标为index的数组元素不加入到candidate集合中
            // 由于candidates数组中存在大量的重复元素，（同时由于之前的排序sort操作，使得candidates数组中元素从小到大进行排序）;
            // ===》 避免重复组合的方法 ：即，当某一步决定跳过某个值m时，需要去跳过所有值为m的数字;
            flushBack(candidates , target , getNext(candidates , index) , candidate , result);

            candidate.add(candidates[index]);
            // 若是选择将下标为index的数组元素加入到candidate集合中的话，即不会出现重复组合;
            // 即，需要去遍历下标为index + 1所对应的数组元素;
            // ===》 即，重复组合只会出现在 选择将下标为index的数组元素不加入到candidate集合中的时候;
            flushBack(candidates , target - candidates[index] , index + 1 ,candidate , result);
            candidate.removeLast();
        }
    }

    private int getNext(int[] candidates , int index) {
        int next = index + 1;
        while(next < candidates.length && candidates[next] == candidates[index]){
            next++;
        }
        return next;
    }
    /**
     * 分析 ：
     * 由于使用了回溯法，回溯法的时间复杂度 :O（2的n次方 ）
     * 时间复杂度 ：O（2的n次方）（n，是根据其回溯的次数来进行判断）
     */
}
